#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cerr<<#x<<':'<<x<<endl
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e6+5;
int n,m,q,k;
int a[N];
int b[N];
int ans;
void dfs(int x){
    if(x>q){
        for(int i=1;i<=n-m+1;i++){
            int flag=1;
            for(int j=1;j<=m;j++){
                if(b[j]!=a[i+j-1]){
                    flag=0;
                    break;
                }
            }
            ans+=flag;
        }
        return;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            int tmp=a[i];
            a[i]=j;
            dfs(x+1);
            a[i]=tmp;
        }
    }
}
signed main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    cin>>n>>m>>q>>k;
    for(int i=1;i<=m;i++) cin>>b[i];
    if(q<k) return cout<<0,0;
    dfs(1);
    cout<<ans;
    return 0;
}